#define _CRT_SECURE_NO_WARNINGS
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode newnode;
//    newnode.next = NULL;
//    struct ListNode* pcur1 = list1;
//    struct ListNode* pcur2 = list2;
//    struct ListNode* newhead = &newnode;
//    struct ListNode* newtail = newhead;
//    while (pcur1 && pcur2)
//    {
//        if (pcur1->val < pcur2->val)
//        {
//            newtail->next = pcur1;
//            newtail = newtail->next;
//            pcur1 = pcur1->next;
//        }
//        else
//        {
//            newtail->next = pcur2;
//            newtail = newtail->next;
//            pcur2 = pcur2->next;
//        }
//    }
//    if (pcur1)
//    {
//        newtail->next = pcur1;
//    }
//    if (pcur2)
//    {
//        newtail->next = pcur2;
//    }
//    return newhead->next;
//}

//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* slow = head;
//    struct ListNode* fast = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//    return slow;
//
//}



//struct ListNode* BuyNode(int n)
//{
//    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
//    if (ret == NULL)
//    {
//        return NULL;
//    }
//    ret->val = n;
//    ret->next = NULL;
//    return ret;
//}
//struct ListNode* CreateCircleList(int n, int m)
//{
//    struct ListNode* phead = BuyNode(1);
//    struct ListNode* ptail = phead;
//    for (int i = 2; i <= n; i++)
//    {
//        ptail->next = BuyNode(i);
//        ptail = ptail->next;
//    }
//    ptail->next = phead;
//    return ptail;
//}
//
//int ysf(int n, int m) {
//     write code here
//    struct ListNode* prev = CreateCircleList(n, m);
//    struct ListNode* pcur = prev->next;
//    int count = 1;
//    while (pcur->next != pcur)
//    {
//        if (count % m == 0)
//        {
//            prev->next = pcur->next;
//            free(pcur);
//            pcur = prev->next;
//            count++;
//            continue;
//        }
//        prev = prev->next;
//        pcur = pcur->next;
//        count++;
//    }
//    return pcur->val;
//
//}


//struct ListNode* partition(struct ListNode* head, int x) {
//    struct ListNode* newhead = NULL;
//    struct ListNode* newtail = NULL;
//    struct ListNode* pcur = head;
//    while (pcur)
//    {
//        if (pcur->val < x)
//        {
//            if (newhead == NULL)
//            {
//                newhead = newtail = pcur;
//                pcur = pcur->next;
//            }
//            else
//            {
//                struct ListNode* tmp = pcur->next;
//                pcur->next = newhead;
//                newhead = pcur;
//                pcur = tmp;
//            }
//
//        }
//        else
//        {
//            if (newhead == NULL)
//            {
//                newhead = newtail = pcur;
//                pcur = pcur->next;
//            }
//            else
//            {
//                newtail->next = pcur;
//                newtail = newtail->next;
//                pcur = pcur->next;
//            }
//        }
//    }
//    if (newtail)
//        newtail->next = NULL;
//    return newhead;
//}